﻿using System;
using System.Collections.Generic;

namespace RNA_Libraries
{
  public static class SequenceProcessing
  {
    public static int LevenshteinDistance(string string1, string string2)
    {
      if (string1 == null) throw new ArgumentNullException("string1");
      if (string2 == null) throw new ArgumentNullException("string2");
      int[,] m = new int[string1.Length + 1, string2.Length + 1];

      for (int i = 0; i <= string1.Length; i++) m[i, 0] = i;
      for (int j = 0; j <= string2.Length; j++) m[0, j] = j;

      for (int i = 1; i <= string1.Length; i++)
        for (int j = 1; j <= string2.Length; j++)
        {
          int diff = (string1[i - 1] == string2[j - 1]) ? 0 : 1;

          m[i, j] = Math.Min(Math.Min(m[i - 1, j] + 1,
                                   m[i, j - 1] + 1),
                                   m[i - 1, j - 1] + diff);
        }

      return m[string1.Length, string2.Length];
    }

    public static int LevenshteinDistance(Sequence s1, Sequence s2)
    {
      if (s1 == null) throw new ArgumentNullException("s1");
      if (s1 == null) throw new ArgumentNullException("s2");
      return LevenshteinDistance(s1.ToString(), s2.ToString());
    }

    /// <summary>
    /// Функция оценивающая затраты на преобразование одной
    /// строки в другую
    /// </summary>
    /// <param name="s1">оцениваемая строка</param>
    /// <param name="s2">исходная строка</param>
    /// <param name="mutList">
    /// здесь будет редакционное предписание
    /// </param>
    /// <returns>оценка затрат на преобразование</returns>
    public static int ExtendedLevensteinDistance(
                                     String s1,
                                     String s2,
                                     int minStart,
                                     ref List<IMutation> mutList)
    {
      const int ValueOfReplace = 1; // Цена замены символа строки
      const int ValueOfDelete = 1; // Цена удаления символа строки
      const int ValueOfInsert = 1; // Цена вставки символа строки

      int i, j;
      int[,] D = new int[s1.Length + 1, s2.Length + 1];

      for (i = 0; i <= s1.Length; i++)
        D[i, 0] = i;
      for (j = 0; j <= s2.Length; j++)
        D[0, j] = j;

      for (i = 1; i <= s1.Length; i++)
      {
        for (j = 1; j <= s2.Length; j++)
        {
          // Если символы совпадают то зачем с ними что-то делать?!
          int Difference = (s1[i - 1] == s2[j - 1]) ? 0 : 1;

          D[i, j] = Math.Min(Math.Min(
                       D[i - 1, j] + ValueOfDelete,
                       D[i, j - 1] + ValueOfInsert),
                       D[i - 1, j - 1] + ValueOfReplace * Difference);
        }
      }

      // Получаем редакционное предписание
      i = s1.Length;
      j = s2.Length;
      while (i > 0 && j > 0 || (i == 0) ^ (j == 0))
      {
        if (i - 1 >= 0 && (D[i, j] == D[i - 1, j] + ValueOfDelete))
        {
          mutList.Add(new DeleteMutation(i - 1 + minStart));
          i--;
        }
        else
          if (j - 1 >= 0 && (D[i, j] == D[i, j - 1] + ValueOfInsert))
          {
            mutList.Add(new InsertMutation(j - 1 + minStart, s2[j - 1].ToString()));
            j--;
          }
          else
          {
            if (s1[i - 1] != s2[j - 1])
              mutList.Add(new ReplaceMutation(i - 1 + minStart, s2[j-1].ToString()));
            else
            {
              mutList.Add(new IdentMutation(i - 1 + minStart));
            }
            i--;
            j--;
          }
      }

      // Инвертируем последовательность редакционного предписания
      // т.к. мы фактически шли задом наперед
      mutList.Reverse();
      return D[s1.Length, s2.Length];
    }

    public static MutationCollection ExtendedLevensteinDistance(Sequence refSeq, Vertex read)
    {
      var mutList = new List<IMutation>();
      var str = refSeq.ToString();
      var l = read.Length;
      var list = new List<string>();
      var cur = 0;
      while (cur+l<=str.Length)
      {
        list.Add(str.Substring(cur,l));
        cur++;
      }
      var minLen = l;
      var minStart = 0;
      cur = 0;
      foreach (var cut in list)
      {
        var len = LevenshteinDistance(cut, read.ToString());
        if (len<minLen)
        {
          minLen = len;
          minStart = cur;
        }
        cur++;
      }

      var length = l;

      var ll = LevenshteinDistance(str.Substring(minStart, length - 1), read.ToString());
      if (ll<minLen && length > 0)
      while (ll<minLen)
      {
        minLen = ll;
        length--;
        ll = LevenshteinDistance(str.Substring(minStart, length - 1), read.ToString());
      }
      else
      {
        if (minStart + length + 1 < str.Length)
        {
          ll = LevenshteinDistance(str.Substring(minStart, length + 1), read.ToString());
          while (ll <= minLen && minStart + length + 1 < str.Length)
          {
            minLen = ll;
            length++;
            ll = LevenshteinDistance(str.Substring(minStart, length + 1), read.ToString());
          }
        }
      }
      
      ExtendedLevensteinDistance(str.Substring(minStart, length), read.ToString(), minStart,ref mutList);
      mutList.ForEach(m => m.Reads.Add(read));

      return new MutationCollection(refSeq, mutList, read);
    }

    public static List<Sequence> GetSplitSeqs(Sequence s, int l)
    {
      var res = new List<Sequence>();
      
      var i = l/2;
      var j = l;
      
      res.Add(new Sequence(s.StartSubstring(i)));
      res.Add(new Sequence(s.StartSubstring(j)));
      
      var str = s.ToString();
      
      while (j + l < s.Length)
      {
        res.Add(new Sequence(str.Substring(i, l)));
        res.Add(new Sequence(str.Substring(j, l)));
        i += l;
        j += l;
      }

      res.Add(new Sequence(s.FinishSubstring(l)));
      
      if (i + l < str.Length)
      {
        res.Add(new Sequence(str.Substring(i,l)));
      }
      
      res.Add(new Sequence(s.FinishSubstring(l/2)));

      return res;
    }
  }
}
